package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Objects;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

public class Main {

	public static void main(String[] args) {

		int[] arr = new int[] { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
		System.out.println(foo1(arr));
	}
	
	
	/**
	 * 解法1
	 * 
	 * @param arr
	 * @return
	 */
	public static int foo1(int[] arr) {

		Objects.requireNonNull(arr, "参数arr不能为null");
		if (arr.length == 0) {
			throw new IllegalArgumentException("参数arr是空数组");
		}
		if (arr.length == 1) {
			return arr[0];
		}
		int result = foo1(arr, arr.length / 2);
		int times = 0;
		for (int i = 0; i < arr.length; i++) {
			if (result == arr[i]) {
				times++;
			}
		}
		if (times * 2 > arr.length) {
			return result;
		}
		return -1;
	}

	private static int foo1(int[] arr, int k) {

		int low = 0;
		int high = arr.length - 1;
		while (low < high) {
			int p = partition(arr, low, high);
			if (k < p) {
				high = p - 1;
			} else if (k > p) {
				low = p + 1;
			} else {
				return arr[k];
			}
		}
		return arr[low];
	}

	private static int partition(int[] arr, int low, int high) {

		int p = arr[low];
		while (low < high) {
			while (low < high && p < arr[high]) {
				high--;
			}
			if (low < high) {
				arr[low++] = arr[high];
			}
			while (low < high && arr[low] < p) {
				low++;
			}
			if (low < high) {
				arr[high--] = arr[low];
			}
		}
		arr[low] = p;
		return low;
	}

	private static void swap(int[] arr, int i, int j) {

		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	/**
	 * 解法2
	 * 
	 * @param arr
	 * @return
	 */
	public static int foo2(int[] arr) {

		Objects.requireNonNull(arr, "参数arr不能为null");
		if (arr.length == 0) {
			throw new IllegalArgumentException("参数arr是空数组");
		}
		if (arr.length == 1) {
			return arr[0];
		}
		int cur = arr[0];
		int counter = 1;
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] == cur) {
				counter++;
			} else {
				if (--counter == 0) {
					cur = arr[i];
					counter = 1;
				}
			}
		}
		int times = 0;
		for (int i = 0; i < arr.length; i++) {
			if (cur == arr[i]) {
				times++;
			}
		}
		if (times * 2 > arr.length) {
			return cur;
		}
		return -1;
	}
}